package com.gxc.graph;

import java.util.*;

/**
 * 迪杰斯特拉算法(Dijkstra)--单元最短路径算法--贪心算法
 */
public class Dijkstra {

    public static void main(String[] args) {
        Graph graph = BreadthFirst.createGraph();

        Map<Node, Integer> map = dijkstra(graph.nodes.get(1));

        //优化可以用自定义堆---堆的升降级
        Map<Node, Integer> map2 = dijkstraUseCustomHeap(graph.nodes.get(1), graph.nodes.keySet().size());
        System.out.println("-----------");
    }

    /**
     * 使用自定义的堆，优化迪杰斯特拉算法
     * @param head
     * @param size
     * @return
     */
    private static Map<Node,Integer> dijkstraUseCustomHeap(Node head, int size) {
        NodeHeap nodeHeap = new NodeHeap(size);
        nodeHeap.addOrUpdateOrIgnore(head, 0);
        Map<Node,Integer> result = new HashMap<>();

        while (!nodeHeap.isEmpty()) {
            NodeRecord record = nodeHeap.pop();
            Node cur = record.node;
            int distance = record.distance;
            for (Edge edge : cur.edges) {
                nodeHeap.addOrUpdateOrIgnore(edge.to, distance+edge.weight);
            }
            result.put(cur, distance);
        }
        return result;
    }


    private static Map<Node, Integer> dijkstra(Node head) {
        // 从head出发到所有点的最小距离
        // key : 从head出发到达key
        // value : 从head出发到达key的最小距离
        // 如果在表中，没有T的记录，含义是从head出发到T这个点的距离为正无穷
        HashMap<Node, Integer> result = new HashMap<>();
        result.put(head, 0);
        //已经算过距离的node
        Set<Node> exist = new HashSet<>();
        //当前距离中最小的node
        Node minNode = getMinDistanceAndUnSelectedNode(result, exist);

        while (minNode != null) {
            int distance = result.get(minNode);
            for (Edge edge : minNode.edges) {
                Node toNode = edge.to;
                if (!result.containsKey(toNode)) {
                    result.put(toNode, distance + edge.weight);
                }
                result.put(toNode, Math.min(distance + edge.weight, result.get(toNode)));
            }
            exist.add(minNode);
            minNode = getMinDistanceAndUnSelectedNode(result, exist);
        }

        return result;
    }

    private static Node getMinDistanceAndUnSelectedNode(HashMap<Node, Integer> result, Set<Node> exist) {
        Integer minDistance = Integer.MAX_VALUE;
        Node minNode = null;

        Iterator<Map.Entry<Node, Integer>> iterator = result.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Node, Integer> next = iterator.next();
            Node node = next.getKey();
            Integer value = next.getValue();
            //node选中，且距离最小
            if (!exist.contains(node) && value<minDistance) {
                minDistance = value;
                minNode = node;
            }
        }
        return minNode;
    }
}
